package dp;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class rob3 {
    public int rob(TreeNode root) {
        int[] result = countNum(root);
        return Math.max(result[0], result[1]);
    }
    public int[] countNum(TreeNode root) {
        //对于每一个节点有两个状态dp[0]不偷当前节点，dp[1]偷当前节点
        int[] dp = new int[2];
        if (root == null) {
            return dp;
        }
        int[] leftDp = countNum(root.left);
        int[] rightDp = countNum(root.right);
        dp[0] = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
        dp[1] = root.val + leftDp[0] + rightDp[0];
        return dp;
    }
}
